package dataStructures.list;

/**
 * A generic Stack. Data is stored internally using SinglelyLinkedNode, which
 * only contains a pointer to the data stored in the node, and a pointer to
 * the next node. Push and pop operations are O(1). This Stack can store
 * null values, note however that the Stack's pop method also returns null
 * when the Stack is empty. Hence, caution should be taken when iterating
 * through the Stack if null values are stored. The recommended way is to use
 * isEmpty() to check if the Stack is empty, instead of checking whether the
 * element returned by the pop method is null.
 * 
 * Fully Tested: Yes
 * Fully Documented: Yes
 * Created: 2011
 * Last Modified: Nov 9, 2011
 * 
 * @param <T> the type of data to store inside the Stack
 * @author Shimu Wu
 */
public class Stack<T> {
  
    private SinglelyLinkedNode<T> first;
    private int size;

    public Stack() {
        this.first = null;
        this.size = 0;
    }

    /**
     * Creates a Stack object with the given firstData on the top of
     * the Stack.
     * @param firstData
     */
    public Stack(T firstData) {
        this();
        push(firstData);
    }

    /**
     * Push an Object of type T onto the top of the stack. Please read the
     * documentation of this class for recommendations about storing null
     * elements in the Stack.
     *
     * @param data the Object of type T to be pushed onto the
     * top of the stack. Null is a valid data for this stack.
     */
    public final void push(T data) {
        SinglelyLinkedNode<T> next = this.first;
        this.first = new SinglelyLinkedNode<T>(data, next);
        size++;
    }

    /**
     * Returns and removes the element at the top of the Stack, returns null
     * if the Stack is empty. Please read the documentation of this class
     * for recommendations about storing null elements in the Stack.
     *
     * @return the element at the top of the Stack.
     */
    public final T pop() {
        if (this.first == null) {
            return null;
        } else {
            T returnData = this.first.data;
            this.first = this.first.next;
            size--;
            return returnData;
        }
    }

    /**
     * Returns the element at the top of the Stack, returns null if the
     * Stack is empty. Please read the documentation of this class
     * for recommendations about storing null elements in the Stack.
     * @return
     */
    public final T peek() {
        if (this.first == null) {
            return null;
        } else {
            return this.first.data;
        }
    }

    /**
     * Returns the number of elements stored in this Stack.
     * 
     * @return the number of elements in this Stack.
     */
    public int getSize() {
        return size;
    }

    /**
     * Returns true if this Stack is empty, false otherwise.
     *
     * @return true if this Stack is empty, false otherwise.
     */
    public boolean isEmpty() {
        return (size == 0);
    }

}
